\section{连分数与平方和}
表整数为二平方和问题， 在 $\S 5.4$ 讨论过， 现可用连分数简洁解答。

\begin{theorem}%定理1
(Legendre) 设 $\sqrt{d}=\left[a_{0}, \overline{a_{1}, \cdots, a_{m-1}, a_{m}}\right]$. 若循环周期 $m=2 s+1$为奇数， 记尾项 $t_{s+1}=\left(P_{s+1}+\sqrt{d}\right) / Q_{s+1}$, 则 $d$ 可表为二平方和：
\[
d=P_{s+1}^{2}+Q_{s+1}^{2}
\]
例如， $\sqrt{41}=[6, \overline{2,2,12}], m=3, s=1, t_{2}=(4+\sqrt{d}) / 5$. 故 $41=4^{2}+5^{2}$.
\end{theorem}

\begin{proof}
 $\sqrt{d}=\left[a_{0}, \overline{a_{1}, \cdots, a_{m-1}, a_{m}}\right]$
\[
=\left[a_{0}, \overline{a_{1}, \cdots,} a_{s}, a_{s}, \cdots, a_{1}, a_{m}\right]
\]
即 $a_{k}=a_{m-k}(k=1, \cdots, m-1)$. 故
\[
\begin{aligned}
& t_{s+1}=\left[\overline{a_{s+1}, \cdots,} a_{m-1}, a_{m}, a_{1}, \cdots, a_{s}\right]=\left[\overline{a_{s}, \cdots, a_{1}, a_{m}, a_{1}, \cdots, a_{s}}\right] \\
& -1 / t_{s+1}^{\prime}=\left[\overline{a_{s}, \cdots, a_{1}, a_{m}, a_{m-1}, \cdots, a_{s+1}}\right]=\left[\overline{a_{s}, \cdots, a_{1}, a_{m}, a_{1}, \cdots, a_{s}}\right]
\end{aligned}
\]
$\left(-1 / t_{s+1}^{\prime}\right.$ 与 $t_{s+1}$ 连分数关系见 $\S 6.3$ 定理 2). 故 $-1 / t_{s+1}^{\prime}=t_{s+1}, t_{s+1}^{\prime} \cdot t_{s+1}=-1$, 即
\[
-1=t_{s+1} t_{s+1}^{\prime}=\left(P_{s+1}+\sqrt{d}\right)\left(P_{s+1}-\sqrt{d}\right) / Q_{s+1}^{2}=\left(P_{s+1}^{2}-d\right) / Q_{s+1}^{2}
\]
\end{proof}

\begin{theorem}%定理2
设素数 $p \equiv 1(\bmod 4)$, 则 $p$ 可表为二平方和。
\end{theorem}
\begin{proof}[证法 1] 我们证明 $\sqrt{p}$ 的连分数周期 $m$ 为奇数， 从而由定理 1 即得。 假设 $\sqrt{p}$ 的连分数周期 $m$ 为偶数， 记 $m-2=2 k$, 则
\[
\begin{aligned}
\sqrt{p}&= \left[a_{0}, \overline{a_{1}, \cdots, a_{m-1}, a_{m}}\right]=\left[a_{0}, \overline{a_{1}, \cdots, a_{k}, a_{k+1}, a_{k}, \cdots, a_{1}, a_{m}}\right]\\
t_{k+1}&= \left[ \overline{a_{k+1}, a_k,\cdots, a_1, a_m, a_1,\cdots, a_k \right],\\
-1 / t_{k+1}^{\prime}&= \left[\overline{a_{k}, \cdots, a_{1}, a_{m}, a_{1}, \cdots, a_{k}, a_{k+1}}\right]
\end{aligned}
\]
$\left(-1 / t_{k+1}^{\prime}\right.$ 与 $t_{k+1}$ 连分数关系见 $\S 6.3$ 定理 2). 故
\[
\begin{gathered}
t_{k+1}=a_{k+1}+\left(-1 / t_{k+1}^{\prime}\right), \quad t_{k+1}+1 / t_{k+1}^{\prime}=a_{k+1} \\
a_{k+1}=t_{k+1}+1 / t_{k+1}^{\prime}=\left[\left(P_{k+1}+\sqrt{p}\right)+\left(P_{k+1}-\sqrt{p}\right)\right] / Q_{k+1}=2 P_{k+1} / Q_{k+1}
\end{gathered}
\]
故 $Q_{k+1} \mid 2 P_{k+1}$. 而我们知道
\[
Q_{k+1} \mid\left(P_{k+1}^{2}-p\right)(\S 6.3 \text { 定理 } 1),
\]
故 $Q_{k+1} \mid 2 p$. 因 $0<Q_{k+1}<2 \sqrt{p}$, 而可设 $p>3$, 故得 $Q_{k+1}=1$ 或 2. 若 $Q_{k+1}=1$, 则 $\sqrt{p}$的连分数周期为 $k+1$ (因 $t_{k+1}$ 分母为 1 , 其小数部分等于 $\sqrt{p}$ 的小数部分), 矛
盾。 故 $Q_{k+1}=2$. 于是
\[
p_{s}^{2}+p q_{s}^{2}= \pm 2
\]
因平方数模 4 为 0 或 1 , 故若 $p \equiv 1(\bmod 4)$, 则上式不可能成立。 这说明， 若 $\sqrt{p}$ 的连分数为偶周期， 则不可能 $p \equiv 1(\bmod 4)$. 其逆否命题为： 若 $p \equiv 1(\bmod$ $4)$, 则 $\sqrt{p}$ 的连分数为奇周期。
\end{proof}

\begin{proof}[证法 2] 首先断言， 对任一实数 $\beta$ 和正整数 $n$, 必存在既约分数 $a / b(0<b$ $\leqslant n)$ 使
\[
\left|\beta-\frac{a}{b}\right|<\frac{1}{b(n+1)}
\]
事实上， 若 $\beta$ 为无理数， 则可取 $\beta$ 的渐近分数 $p_{m} / q_{m}$ 使 $q_{m} \leqslant n<q_{m+1}$, 故由 $\S 6.1$定理 2 知
\[
\left|\beta-\frac{p_{m}}{q_{m}}\right|<\frac{1}{q_{m} q_{m+1}} \leqslant \frac{1}{q_{m}(n+1)}
\]
若 $\beta$ 为有理数， 只要 $n<q_{m+1}$ 则上述仍有效; 而若所有的 $q_{k}$ 都小于 $n$, 取 $\beta=a / b$即可。

由 $p \equiv 1(\bmod 4)$, 知 $y^{2}=-1$ 有整数解。 由断言知， 有 $a / b(0<b \leqslant n=$ $[\sqrt{p}]$ ) 使得
\[
\frac{|b y+a p|}{b p}=\left|-\frac{y}{p}-\frac{a}{b}\right|<\frac{1}{b([\sqrt{p}]+1)}<\frac{1}{\sqrt{p} b}
\]
故知 $|c|=|b y+a p| \leqslant \sqrt{p}$. 于是 $b^{2}+c^{2} \leqslant p+p$, 而 $b^{2}+c^{2} \equiv b^{2}+y^{2} b^{2} \equiv 0(\bmod p)$,得到
\[
b^{2}+c^{2}=p
\]
\end{proof}


\begin{comment*}%评述
连分数的历史古老， Euclid 的《几何原本》中辗转相除即生成连分数。 连分数的引人十分自然， 人常用数的整数部分代此数， 若要再精确一点，就再给出其小数部分倒数的整数部分， 等等， 即为连分数。 用连分数表示实数，比用十进小数更合理：因为这“ 10 ”的选取不自然， 不唯一， 还可选取二进， 八进等; 而连分数超脱了这些， 纯粹。 连分数步步皆是最佳逼近， 而十进小数不然。 “小分子分母”分数的连分数皆短小 (而小数不然). 当且仅当分数的连分数有限（而小数不然）. 当且仅当二次数（开方根）的连分数循环（而小数循环为分数一一可见， 连分数处理开方之易， 犹如小数之于分数一般). 更有不可计数的应用： 逼近与代数数超越数、不定方程、天文、历法、乐律， 等等。论数者单赞这“连分数之神奇”曰：

莲花步步最可人，调罢律吕定天文。

轻收分数归有限， 却教开方借花魂。
\end{comment*}

